﻿#include <iostream>
#include <vector>
#include <string>
#include <set>

#include <algorithm>
using namespace std;

//求正数数组的最小不可组成和
//https://www.nowcoder.com/questionTerminal/296c2c18037843a7b719cf4c9c0144e4
//class Solution {
//public:
//    /**
//     *	正数数组中的最小不可组成和
//     *	输入：正数数组arr
//     *	返回：正数数组中的最小不可组成和
//     */
//    int getFirstUnFormedNum(vector<int> arr, int len) {
//        long long min = arr[0];
//        long long max = 0;
//        for (const auto& x : arr) //取最大最小
//        {
//            if (min > x) min = x;
//            max += x;
//        }
//
//        set<long long> s;
//        vector<long long> v;
//        for (int i = 0; i < len; ++i)
//        {
//            for (auto sit = s.begin(); sit != s.end(); ++sit) //将已存入的数再与i下标值组合
//            {
//                v.push_back(*sit + arr[i]);
//            }
//            s.insert(v.begin(), v.end()); //插入最新组合的数但不重复
//            s.insert(arr[i]);
//            v.clear(); //清空本次组合-下次再次组合
//        }
//
//        里面可能存在多个不可组成和 - 找最小的
//        for (int i = min; i <= max; ++i) //有序遍历 返回最小的不可组成和
//        {
//            if (s.find(i) == s.end())
//                return i;
//        }
//
//        return max + 1;
//    }
//};

//有假币 - 未完成，算法学习(分析题目+列举+动态方程)
//https://www.nowcoder.com/questionTerminal/1d18c0841e64454cbc3afaea05e2f63c
//int main()
//{
//    long long num = 0;
//    while (cin >> num)
//    {
//        if (!num) break;
//        int count = 0;
//        while (num > 1)
//        {
//            count += 1;
//            //每次把num分为三等分去判断 如果num>1 判断最坏的情况
//            //1 1 0 两个硬币称一次就可以了 - 1
//            //1 1 1 三个硬币称任意两个就行 - 1
//            //2 1 1 四个硬币称两个1再称剩下的两个 - 2
//            //2 2 1 五个硬币先称两个2再从两个2中称两个1 - 2
//            //2 2 2 六个称其中两个2 再从两个2中称两个1 - 2
//            //3 2 2 七个称其中两个2，再称剩下3个 - 2
//            //3 3 2 八个称其中两个3 在从其中一个3中称 - 2
//            //3 3 3 九个先称其中两个3然后再从任意一个3中称 - 2
//            //4 3 3 先称其中两个3，再从4中称两个2再从2中称两个1
//            num = num / 3 + (num % 3 > 0); //由于无论分成三份是多出一个还是两个，都需要称重，所以统一按1处理
//        }
//        cout << count << endl;
//    }
//    return 0;
//}